Suchergebnisse

ABSTRACTDiscriminant analysis is an important tool for practical problem solving. Classical statistical applications have been joined recently by applications in the fields of management science and artificial intelligence. In a departure from the methodology of statistics, a series of proposals have appeared for capturing the goals of discriminant analysis in a collection of linear programming formulations. The evolution of these formulations has brought advances that have removed a number of initial shortcomings and deepened our understanding of how these models differ in essential ways from other familiar classes of LP formulations. We will demonstrate, however, that the full power of the LP discriminant analysis models has not been achieved, due to a previously undetected distortion that inhibits the quality of solutions generated. The purpose of this paper is to show how to eliminate this distortion and thereby increase the scope and flexibility of these models. We additionally show how these outcomes open the door to special model manipulations and simplifications, including the use of a successive goal method for establishing a series of conditional objectives to achieve improved discrimination.

ABSTRACTThis paper proposes a class of surrogate constraint heuristics for obtaining approximate, near optimal solutions to integer programming problems. These heuristics are based on a simple framework that illuminates the character of several earlier heuristic proposals and provides a variety of new alternatives. The paper also proposes additional heuristics that can be used either to supplement the surrogate constraint procedures or to provide independent solution strategies. Preliminary computational results are reported for applying one of these alternatives to a class of nonlinear generalized set covering problems involving approximately 100 constraints and 300–500 integer variables. The solutions obtained by the tested procedure had objective function values twice as good as values obtained by standard approaches (e.g., reducing the best objective function values of other methods from 85 to 40 on the average. Total solution time for the tested procedure ranged from ten to twenty seconds on the CDC 6600.

AbstractA special matching problem arising in industry is shown to be solvable by an algorithm of the form: match objects ai and bj if they satisfy a local optirnality criterion based on a ranking of currently unmatched objects. When no ai and bi remain that can be matched, the largest number of acceptable matches has been found.

ABSTRACTIn certain settings, difficulties arise that limit the effectiveness of LP formulations for the discriminant problem. Explanations and possible remedies have been offered, but these have had only limited success. We provide a simple way to overcome these problems based on an appropriate use and interpretation of normalizations. In addition, we demonstrate a normalization that is invariant under all translations of the problem data, providing a stability property not shared by previous approaches. Finally, we discuss the possibility of using more general models to improve discrimination.

ABSTRACTThe two‐group discriminant problem has applications in many areas, for example, differentiating between good credit risks and poor ones, between promising new firms and those likely to fail, or between patients with strong prospects for recovery and those highly at risk. To expand our tools for dealing with such problems, we propose a class of nonpara‐metric discriminant procedures based on linear programming (LP). Although these procedures have attracted considerable attention recently, only a limited number of computational studies have examined the relative merits of alternative formulations. In this paper we provide a detailed study of three contrasting formulations for the two‐group problem. The experimental design provides a variety of test conditions involving both normal and nonnormal populations. Our results establish the LP model which seeks to minimize the sum of deviations beyond the two‐group boundary as a promising alternative to more conventional linear discriminant techniques.

We propose an alternative solution to the discriminant problem, one that requires little more than a minimum familiarity with linear programming. The approach shows promise for eliminating the complexities of conventional statistical approaches without sacrificing the essential power of existing methods.

AbstractMixed integer programming problems arising in practice often contain special structures such as imbedded networks and multiple choice constraints. Easily derived inequalities are given that can be used to reduce the range of admissible solutions for such problems.

A number of articles on managerial decision making have addressed the issue of whether or not to round a fractional solution to obtain a solution for a problem involving discrete alternatives. (An example is the problem in which the decision maker must select exactly one of several investment alternatives, but attaches no meaning to selecting two‐thirds of one alternative and one‐third of another.) Those articles which suggest that rounding can lead to undesirable answers are seemingly supported by the numerous "textbook examples" that purport to illustrate the dangers of rounding. However, the standard examples in which rounding fails to give a workable solution involve only a few rounding possibilities (usually two or four) and do not come from real world applications. Hence, it is questionable whether they provide any insight about what is likely to occur in a practical setting. This note fills a gap in previous discussions of rounding by providing two easily understood examples that dramatically portray the difficulties that rounding can encounter. The first example belongs to an important class of practical problems. We illustrate that rounding fails not only for this example, but also fails for all problems in its class. The second example is a unique "showcase" problem which can be summarized by a 5 times 5 cost matrix. This problem contains more than a million rounding alternatives, all of them infeasible! Following these examples, we present a "rounding paradox" and we show that its resolution gives analytical support to the conclusion that rounding will produce grave difficulties in a wide variety of practical situations.

AbstractRecent efforts in the field of dynamic programming have explored the feasibility of solving certain classes of integer programming problems by recursive algorithms. Special recursive algorithms have been shown to be particularly effective for problems possessing a 0–1 attribute matrix displaying the "nesting property" studied by, Ignall and Veinott in inventory theory and by Glover in network flows.This paper extends the class of problem structures that has been shown amenable to recursive exploitation by providing an efficient dynamic programming approach for a general transportation scheduling problem. In particular, we provide alternative formulations lor the scheduling problem and show how the most general of these formulations can be readily solved vis a vis recursive techniques.

ABSTRACTDiscriminant analysis is relevant to business decision making in a variety of contexts, such as when one decides to make or buy a specified component, fund a venture project, or hire a particular person. Potential applications in artificial intelligence, particularly in the area of pattern recognition, have further underscored the importance of the field. A recent innovation in discriminant analysis is provided by special linear programming (LP) models, which offer attractive alternatives to classical statistical approaches. The scope of application in which discriminant analysis can be advantageously employed is broadened by the flexibility to tailor parameters in the LP approaches to reflect diverse goals and by the power to explore the sensitivity of these parameters. In spite of the promise of the LP formulations, however, limitations to their effectiveness have been uncovered in certain settings. A recent advance involving a normalization construct removes some of the limitations but entails solving the LP model twice (to allow for different signs of a normalization constant) and does not yield equivalent solutions for different rotations of the problem data. This paper introduces a new model and a new class of normalizations that remedy both remaining limitations, making it possible to take advantage of the modeling capabilities of the LP formulations without the attendant shortcomings encountered by earlier investigations. Our development shows by empirical testing and illustrative analysis that the quality of solutions from LP discriminant approaches is more favorable (relative to the classical model) than previously supposed.